home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / bipl.zip / PROGS.ZIP / RSG.ICN < prev    next >
Text File  |  1992-09-28  |  11KB  |  380 lines
  1. ############################################################################
  2. #
  3. #    File:     rsg.icn
  4. #
  5. #    Subject:  Program to generate randomly selected sentences
  6. #
  7. #    Author:   Ralph E. Griswold
  8. #
  9. #    Date:     June 10, 1988
  10. #
  11. ###########################################################################
  12. #  
  13. #     This program generates randomly selected strings (``sen-
  14. #  tences'') from a grammar specified by the user.  Grammars are
  15. #  basically context-free and resemble BNF in form, although there
  16. #  are a number of extensions.
  17. #  
  18. #     The program works interactively, allowing the user to build,
  19. #  test, modify, and save grammars. Input to rsg consists of various
  20. #  kinds of specifications, which can be intermixed:
  21. #  
  22. #     Productions define nonterminal symbols in a syntax similar to
  23. #  the rewriting rules of BNF with various alternatives consisting
  24. #  of the concatenation of nonterminal and terminal symbols.  Gen-
  25. #  eration specifications cause the generation of a specified number
  26. #  of sentences from the language defined by a given nonterminal
  27. #  symbol.  Grammar output specifications cause the definition of a
  28. #  specified nonterminal or the entire current grammar to be written
  29. #  to a given file.  Source specifications cause subsequent input to
  30. #  be read from a specified file.
  31. #  
  32. #     In addition, any line beginning with # is considered to be a
  33. #  comment, while any line beginning with = causes the rest of that
  34. #  line to be used subsequently as a prompt to the user whenever rsg
  35. #  is ready for input (there normally is no prompt). A line consist-
  36. #  ing of a single = stops prompting.
  37. #  
  38. #  Productions: Examples of productions are:
  39. #  
  40. #          <expr>::=<term>|<term>+<expr>
  41. #          <term>::=<elem>|<elem>*<term>
  42. #          <elem>::=x|y|z|(<expr>)
  43. #  
  44. #  Productions may occur in any order. The definition for a nonter-
  45. #  minal symbol can be changed by specifying a new production for
  46. #  it.
  47. #  
  48. #     There are a number of special devices to facilitate the defin-
  49. #  ition of grammars, including eight predefined, built-in nontermi-
  50. #  nal symbols:
  51. #     symbol   definition
  52. #     <lb>     <
  53. #     <rb>     >
  54. #     <vb>     |
  55. #     <nl>     newline
  56. #     <>       empty string
  57. #     <&lcase> any single lowercase letter
  58. #     <&ucase> any single uppercase letter
  59. #     <&digit> any single digit
  60. #  
  61. #  In addition, if the string between a < and a > begins and ends
  62. #  with a single quotation mark, it stands for any single character
  63. #  between the quotation marks. For example,
  64. #  
  65. #          <'xyz'>
  66. #  
  67. #  is equivalent to
  68. #  
  69. #          x|y|z
  70. #  
  71. #  Generation Specifications: A generation specification consists of
  72. #  a nonterminal symbol followed by a nonnegative integer. An exam-
  73. #  ple is
  74. #  
  75. #          <expr>10
  76. #  
  77. #  which specifies the generation of 10 <expr>s. If the integer is
  78. #  omitted, it is assumed to be 1. Generated sentences are written
  79. #  to standard output.
  80. #  
  81. #  Grammar Output Specifications: A grammar output specification
  82. #  consists of a nonterminal symbol, followed by ->, followed by a
  83. #  file name. Such a specification causes the current definition of
  84. #  the nonterminal symbol to be written to the given file. If the
  85. #  file is omitted, standard output is assumed. If the nonterminal
  86. #  symbol is omitted, the entire grammar is written out. Thus,
  87. #  
  88. #          ->
  89. #  
  90. #  causes the entire grammar to be written to standard output.
  91. #  
  92. #  Source Specifications: A source specification consists of @ fol-
  93. #  lowed by a file name.  Subsequent input is read from that file.
  94. #  When an end of file is encountered, input reverts to the previous
  95. #  file. Input files can be nested.
  96. #  
  97. #  Options: The following options are available:
  98. #  
  99. #       -s n Set the seed for random generation to n.  The default
  100. #            seed is 0.
  101. #  
  102. #       -l n Terminate generation if the number of symbols remaining
  103. #            to be processed exceeds n. The default is limit is 1000.
  104. #  
  105. #       -t   Trace the generation of sentences. Trace output goes to
  106. #            standard error output.
  107. #  
  108. #  Diagnostics: Syntactically erroneous input lines are noted but
  109. #  are otherwise ignored.  Specifications for a file that cannot be
  110. #  opened are noted and treated as erroneous.
  111. #  
  112. #     If an undefined nonterminal symbol is encountered during gen-
  113. #  eration, an error message that identifies the undefined symbol is
  114. #  produced, followed by the partial sentence generated to that
  115. #  point. Exceeding the limit of symbols remaining to be generated
  116. #  as specified by the -l option is handled similarly.
  117. #  
  118. #  Caveats: Generation may fail to terminate because of a loop in
  119. #  the rewriting rules or, more seriously, because of the progres-
  120. #  sive accumulation of nonterminal symbols. The latter problem can
  121. #  be identified by using the -t option and controlled by using the
  122. #  -l option. The problem often can be circumvented by duplicating
  123. #  alternatives that lead to fewer rather than more nonterminal sym-
  124. #  bols. For example, changing
  125. #  
  126. #          <term>::=<elem>|<elem>*<term>
  127. #  
  128. #  to
  129. #  
  130. #          <term>::=<elem>|<elem>|<elem>*<term>
  131. #  
  132. #  increases the probability of selecting <elem> from 1/2 to 2/3.
  133. #  
  134. #     There are many possible extensions to the program. One of the
  135. #  most useful would be a way to specify the probability of select-
  136. #  ing an alternative.
  137. #  
  138. ############################################################################
  139. #
  140. #  Links: options
  141. #
  142. ############################################################################
  143.  
  144. link options
  145.  
  146. global defs, ifile, in, limit, prompt, tswitch
  147.  
  148. record nonterm(name)
  149. record charset(chars)
  150.  
  151. procedure main(args)
  152.    local line, plist, s, opts
  153.                     # procedures to try on input lines
  154.    plist := [define,generate,grammar,source,comment,prompter,error]
  155.    defs := table()            # table of definitions
  156.    defs["lb"] := [["<"]]        # built-in definitions
  157.    defs["rb"] := [[">"]]
  158.    defs["vb"] := [["|"]]
  159.    defs["nl"] := [["\n"]]
  160.    defs[""] := [[""]]
  161.    defs["&lcase"] := [[charset(&lcase)]]
  162.    defs["&ucase"] := [[charset(&ucase)]]
  163.    defs["&digit"] := [[charset(&digits)]]
  164.  
  165.    opts := options(args,"tl+s+")
  166.    limit := \opts["l"] | 1000
  167.    tswitch := \opts["t"]
  168.    &random := \opts["s"]
  169.  
  170.    ifile := [&input]            # stack of input files
  171.    prompt := ""
  172.    while in := pop(ifile) do {        # process all files
  173.       repeat {
  174.          if *prompt ~= 0 then writes(prompt)
  175.          line := read(in) | break
  176.          while line[-1] == "\\" do line := line[1:-1] || read(in) | break
  177.          (!plist)(line)
  178.          }
  179.       close(in)
  180.       }
  181. end
  182.  
  183. #  process alternatives
  184. #
  185. procedure alts(defn)
  186.    local alist
  187.    alist := []
  188.    defn ? while put(alist,syms(tab(upto('|') | 0))) do move(1) | break
  189.    return alist
  190. end
  191.  
  192. #  look for comment
  193. #
  194. procedure comment(line)
  195.    if line[1] == "#" then return
  196. end
  197.  
  198. #  look for definition
  199. #
  200. procedure define(line)
  201.    return line ?
  202.       defs[(="<",tab(find(">::=")))] := (move(4),alts(tab(0)))
  203. end
  204.  
  205. #  define nonterminal
  206. #
  207. procedure defnon(sym)
  208.    local chars, name
  209.    if sym ? {
  210.       ="'" &
  211.       chars := cset(tab(-1)) &
  212.       ="'"
  213.       }
  214.    then return charset(chars)
  215.    else return nonterm(sym)
  216. end
  217.  
  218. #  note erroneous input line
  219. #
  220. procedure error(line)
  221.    write("*** erroneous line:  ",line)
  222.    return
  223. end
  224.  
  225. #  generate sentences
  226. #
  227. procedure gener(goal)
  228.    local pending, symbol
  229.    pending := [nonterm(goal)]
  230.    while symbol := get(pending) do {
  231.       if \tswitch then
  232.          write(&errout,symimage(symbol),listimage(pending))
  233.       case type(symbol) of {
  234.          "string":   writes(symbol)
  235.          "charset":  writes(?symbol.chars)
  236.          "nonterm":  {
  237.             pending := ?\defs[symbol.name] ||| pending | {
  238.                write(&errout,"*** undefined nonterminal:  <",symbol.name,">")
  239.                break 
  240.                }
  241.             if *pending > \limit then {
  242.                write(&errout,"*** excessive symbols remaining")
  243.                break 
  244.                }
  245.             }
  246.          }
  247.       }
  248.    write()
  249. end
  250.  
  251. #  look for generation specification
  252. #
  253. procedure generate(line)
  254.    local goal, count
  255.    if line ? {
  256.       ="<" &
  257.       goal := tab(upto('>')) \ 1 &
  258.       move(1) &
  259.       count := (pos(0) & 1) | integer(tab(0))
  260.       }
  261.    then {
  262.       every 1 to count do
  263.          gener(goal)
  264.       return
  265.       }
  266.    else fail
  267. end
  268.  
  269. #  get right hand side of production
  270. #
  271. procedure getrhs(a)
  272.    local rhs
  273.    rhs := ""
  274.    every rhs ||:= listimage(!a) || "|"
  275.    return rhs[1:-1]
  276. end
  277.  
  278. #  look for request to write out grammar
  279. #
  280. procedure grammar(line)
  281.    local file, out, name
  282.    if line ? {
  283.       name := tab(find("->")) &
  284.       move(2) &
  285.       file := tab(0) &
  286.       out := if *file = 0 then &output else {
  287.          open(file,"w") | {
  288.             write(&errout,"*** cannot open ",file)
  289.             fail
  290.             }
  291.          }
  292.       }
  293.    then {
  294.       (*name = 0) | (name[1] == "<" & name[-1] == ">") | fail
  295.       pwrite(name,out)
  296.       if *file ~= 0 then close(out)
  297.       return
  298.       }
  299.    else fail
  300. end
  301.  
  302. #  produce image of list of grammar symbols
  303. #
  304. procedure listimage(a)
  305.    local s, x
  306.    s := ""
  307.    every x := !a do
  308.       s ||:= symimage(x)
  309.    return s
  310. end
  311.  
  312. #  look for new prompt symbol
  313. #
  314. procedure prompter(line)
  315.    if line[1] == "=" then {
  316.       prompt := line[2:0]
  317.       return
  318.       }
  319. end
  320.  
  321. #  write out grammar
  322. #
  323. procedure pwrite(name,ofile)
  324.    local nt, a
  325.    static builtin
  326.    initial builtin := ["lb","rb","vb","nl","","&lcase","&ucase","&digit"]
  327.    if *name = 0 then {
  328.       a := sort(defs,3)
  329.       while nt := get(a) do {
  330.          if nt == !builtin then {
  331.             get(a)
  332.             next
  333.             }
  334.          write(ofile,"<",nt,">::=",getrhs(get(a)))
  335.          }
  336.       }
  337.    else write(ofile,name,"::=",getrhs(\defs[name[2:-1]])) |
  338.       write("*** undefined nonterminal:  ",name)
  339. end
  340.  
  341. #  look for file with input
  342. #
  343. procedure source(line)
  344.    local file, new
  345.  
  346.    return line ? {
  347.       if ="@" then {
  348.          new := open(file := tab(0)) | {
  349.             write(&errout,"*** cannot open ",file)
  350.             fail
  351.             }
  352.          push(ifile,in) &
  353.          in := new
  354.          return
  355.          }
  356.       }
  357. end
  358.  
  359. #  produce string image of grammar symbol
  360. #
  361. procedure symimage(x)
  362.    return case type(x) of {
  363.       "string":   x
  364.       "nonterm":  "<" || x.name || ">"
  365.       "charset":  "<'" || x.chars || "'>"
  366.       }
  367. end
  368.  
  369. #  process the symbols in an alternative
  370. #
  371. procedure syms(alt)
  372.    local slist
  373.    static nonbrack
  374.    initial nonbrack := ~'<'
  375.    slist := []
  376.    alt ? while put(slist,tab(many(nonbrack)) |
  377.       defnon(2(="<",tab(upto('>')),move(1))))
  378.    return slist
  379. end
  380.